package main

import (
	"fmt"
)

// 重建二叉树

type Node struct {
	value int64
	left *Node
	right *Node
}

func main() {
	preOrder := []int64{1,2,4,7,3,5,6,8}
	inOrder := []int64{4,7,2,1,5,3,8,6}

	tree := constructBTree(preOrder, inOrder)
	preCatTree(tree) //先序遍历
	inCatTree(tree) //中序遍历
}

func preCatTree(t *Node) {
	fmt.Println(t.value)
	if t.left!=nil{
		preCatTree(t.left)
	}
	if t.right!=nil{
		preCatTree(t.right)
	}
}
func inCatTree(t *Node) {
	if t.left!=nil{
		inCatTree(t.left)
	}
	fmt.Println(t.value)
	if t.right!=nil{
		inCatTree(t.right)
	}
}

func constructBTree(preOrder, inOrder []int64) *Node{
	l := len(preOrder)
	if l == 0{
		return  nil
	}

	root := &Node{
		value:preOrder[0],
	}
	if l == 1{
		return root
	}

	leftLen := 0
	rightLen := 0
	for _,v := range inOrder{
		if v == root.value{
			break
		}
		leftLen++
	}
	rightLen = l - leftLen - 1

	if leftLen > 0{
		fmt.Println("左子树",preOrder[1:leftLen+1], inOrder[0:leftLen])
		root.left = constructBTree(preOrder[1:leftLen+1], inOrder[0:leftLen])
	}
	if rightLen >0{
		fmt.Println("右子树",preOrder[leftLen+1:], inOrder[leftLen+1:])
		root.right = constructBTree(preOrder[leftLen+1:], inOrder[leftLen+1:])
	}

	return root
}